package leetcode.level2;

import java.util.ArrayList;
import java.util.List;

/**
 * 3. 无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * @author ben
 * @date 2021-10-25 11:46:56 CST
 */
public class Solution3 {

    public int lengthOfLongestSubstring(String s) {
    	return lengthOfLongestSubstring1(s);
    }
    
    /**
     * 第一个实现版本
     * @author ben
     * @date 2021-10-25 11:46:45 CST
     * @param s
     * @return
     */
    private int lengthOfLongestSubstring1(String s) {
    	int max = 0;
    	
    	// ArrayList消耗内存更少，执行时间更快
    	List<Character> list = new ArrayList<>();
    	// 内存消耗：40.3 MB , 在所有 Java 提交中击败了 5.00% 的用户
//    	List<Character> list = new LinkedList<>();
    	int len = s.length();
    	int maxtemp = 0;
    	for (int i=0; i<len; i++) {
    		Character c = s.charAt(i);
    		
    		if (list.contains(c)) {
    			int idx = list.indexOf(c);
//    			System.out.println("idx=" + idx);
//    			System.out.println("list=" + list);
    			// 新list：第一次重复的地方截取
    			list = list.subList(idx + 1, list.size());
//    			System.out.println("list=" + list);
    			
    			list.add(c);
    			maxtemp = list.size();
    			if (maxtemp > max) {
    				max = maxtemp;
    			}
//    			System.out.println("list=" + list);
    		} else {
    			list.add(c);
    			maxtemp++;
    			if (maxtemp > max) {
    				max = maxtemp;
    			}
    		}
    	}
    	
    	return max;
    }

	public static void main(String[] args) {
		Solution3 s = new Solution3();
		
		// 3
		System.out.println(s.lengthOfLongestSubstring("abcabcbb"));
		// 1
		System.out.println(s.lengthOfLongestSubstring("bbbbb"));
		// 3
		System.out.println(s.lengthOfLongestSubstring("pwwkew"));
		// 0
		System.out.println(s.lengthOfLongestSubstring(""));
		// 3
		System.out.println(s.lengthOfLongestSubstring("dvdf"));
		// 3
		System.out.println(s.lengthOfLongestSubstring("advdf"));
	}

}
